#include "../include/BSTree.h"

struct BTreeNode *createBSTree(ElementType a[],int n){
	BTreeNode *root;
	root = NULL;
	int i;
	for(i =0;i<n;i++){
		root = insertElement(root,a[i]);
	}
	return root;

}


struct BTreeNode * insertElement(BTreeNode *root,ElementType n){
	BTreeNode *left,*right;
	if(root == NULL){
		root = createNode(n);
	}else if(root->value > n){
		left = insertElement(root->leftNode,n);
		root->leftNode = left;
	}else {
		right = insertElement(root->rightNode,n);
		root->rightNode = right;
	}	
	return root;	
}


struct BTreeNode * deleteElement(BTreeNode *tree,ElementType n){
	BTreeNode *root,*result ;
	if(tree->value ==n){
		result = tree;
		if(tree->leftNode == NULL && tree->rightNode ==NULL)
			return NULL;
		else if(tree->leftNode ==NULL){
			BTreeNode *target,*pre;
			pre = target = tree->rightNode;
			while(target->leftNode!=NULL){
				pre = target;
				target = target->leftNode;
			}
			target->leftNode = tree->leftNode;
			if(target != tree->rightNode){
				target->rightNode = tree->rightNode;
				pre->leftNode = NULL;
			}
			root =  target;
		}else{
			BTreeNode *target,*pre;
			pre = target = tree->leftNode;
			while(target->rightNode != NULL){
				pre = target;
				target = target->rightNode;
			}			
			target->rightNode = tree->rightNode;
			if(tree->leftNode != target){
				target->leftNode = tree->leftNode;
				pre->rightNode = NULL;
			}
			root = target;
		}	
		free(result);
		return root;
	}else if( tree->value > n){
		if(tree->leftNode !=NULL)
			tree->leftNode = deleteElement(tree->leftNode,n);
	}else{
		if(tree->rightNode != NULL)
			tree->rightNode = deleteElement(tree->rightNode,n);
	}
	return tree;
}


BTreeNode *getList(BTreeNode *root){
	BTreeNode *left,*right,*start;
	if(root->leftNode==NULL){
		start = root;
	}else if(root->leftNode != NULL){
		left = getList(root->leftNode);
		start = left;
		while(left->leftNode != NULL){
			left = left->leftNode;
		}
		left->leftNode = root;
	}
	if(root->rightNode != NULL){
		right = getList(root->rightNode);
		root->leftNode = right;
	}else
		root->leftNode = NULL;
	root->rightNode = NULL;
	return start;
}

BTreeNode *changeIntoList(BTreeNode *root){
	BTreeNode *start;
	if(root ==NULL)
		return NULL;
	start = getList(root);
	return start;
}

